package Array_and_String;

/*
最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/conm7/
 */

public class _32最长回文子串 {
    public static void main(String[] args) {

        String s1 = "babad";
        String s2 = "aaaa";

//        System.out.println(longestPalindrome2(s1));
        System.out.println(longestPalindrome2(s2));

    }

    //方法一:暴力枚举
    //有点 中心扩展 的意思
    public static String longestPalindrome(String s) {
        //遍历每一个和每两个字母进行前后对比确认回文串，对比答案回文串，留下最长回文串
        String res = "";
        //每个字母
        for (int i = 0; i < s.length(); i++) {
            int left = i, right = i;
            while (left >= -1 && right <= s.length()) {
                if (left == -1 || right == s.length()) {
                    left++;
                    right--;
                    if (right - left + 1 > res.length()) {
                        res = s.substring(left, right + 1);
                    }
                    break;
                }

                if (s.charAt(left) != s.charAt(right)) {
                    if (right - left - 1 > res.length()) {
                        res = s.substring(left + 1, right);
                    }
                    break;
                } else {
                    left--;
                    right++;
                }
            }
        }
        //每两个字母
        for (int i = 0; i < s.length(); i++) {
            int left = i, right = i + 1;
            while (left >= -1 && right <= s.length()) {
                if (left == -1 || right == s.length()) {
                    left++;
                    right--;
                    if (right - left + 1 > res.length()) {
                        res = s.substring(left, right + 1);
                    }
                    break;
                }

                if (s.charAt(left) != s.charAt(right)) {
                    if (right - left - 1 > res.length()) {
                        res = s.substring(left + 1, right);
                    }
                    break;
                } else {
                    left--;
                    right++;
                }
            }
        }
        return res;
    }

    //方法二:动态规划
    public static String longestPalindrome2(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        //记录i~j的子串是否为回文串的数组
        boolean[][] dp = new boolean[s.length()][s.length()];
        //每个字母必定是回文串
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        //根据子串长度进行遍历字符串
        int maxLen = 1;
        int start = 0;
        for(int L = 2; L <= s.length(); L++){
            int left = 0;
            for(left = 0; left < s.length(); left++){
                if(left + L -1 >= s.length()){
                    break;
                }
                if(s.charAt(left) == s.charAt(left+L- 1)){
                    if(L <= 3){
                        dp[left][left+L- 1] = true;
                        if (maxLen < L){
                            maxLen = L;
                            start = left;
                        }
                    }else {
                        if(dp[left + 1][left+L - 2]){
                            dp[left][left + L - 1] = true;
                            if (maxLen < L){
                                maxLen = L;
                                start = left;
                            }
                        }
                    }
                }
            }
        }

        return s.substring(start, start + maxLen);


    }

        //官解:动态规划
        public String longestPalindrome3(String s) {
            int len = s.length();
            if (len < 2) {
                return s;
            }

            int maxLen = 1;
            int begin = 0;
            // dp[i][j] 表示 s[i..j] 是否是回文串
            boolean[][] dp = new boolean[len][len];
            // 初始化：所有长度为 1 的子串都是回文串
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }

            char[] charArray = s.toCharArray();
            // 递推开始
            // 先枚举子串长度
            for (int L = 2; L <= len; L++) {
                // 枚举左边界，左边界的上限设置可以宽松一些
                for (int i = 0; i < len; i++) {
                    // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                    int j = L + i - 1;
                    // 如果右边界越界，就可以退出当前循环
                    if (j >= len) {
                        break;
                    }

                    if (charArray[i] != charArray[j]) {
                        dp[i][j] = false;
                    } else {
                        if (j - i < 3) {
                            dp[i][j] = true;
                        } else {
                            dp[i][j] = dp[i + 1][j - 1];
                        }
                    }

                    // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                    if (dp[i][j] && j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        begin = i;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }
    }

